{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 14,
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# 决策树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "outputs": [],
   "source": [
    "# 贷款申请样本数据表\n",
    "# 15个样本，其中有4个特征，1个类别\n",
    "# 年龄：青年 5； 中年 5； 老年 5\n",
    "# 有工作：有 5 ； 否 10\n",
    "# 有自己的房子： 是 6 ； 否 9\n",
    "# 信贷情况： 非常好 4 ； 好 6 ； 一般 5\n",
    "# 类别： 否 6 ；是 9"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "##  特征选择"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "###  1、信息增益\n",
    "#### 经验熵 H(D)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H(D):\n"
     ]
    }
   ],
   "source": [
    "# 经验熵H(D)是不加特征的\n",
    "# 表示对数据集D进行分类的不确定性\n",
    "print('H(D):')\n",
    "-1 * 6 / 15 * np.log2(6 / 15) - 1 * 9 / 15 * np.log2(9 / 15)\n",
    "HD = -1 * 6 / 15 * np.log2(6 / 15) - 1 * 9 / 15 * np.log2(9 / 15)\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### 条件经验熵 H(D|A)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H(D1): 0.9709505944546686\n",
      "H(D2): 0.9709505944546686\n",
      "H(D3): 0.7219280948873623\n"
     ]
    }
   ],
   "source": [
    "# 加上特征\n",
    "# 年龄 D1 青年  5(否3 是2)； D2 中年 5(否2 是3)；  D3 老年 5(否1 是4)\n",
    "HD1 = -3 / 5 * np.log2(3 / 5) - 2 / 5 * np.log2(2 / 5)\n",
    "HD2 = -2 / 5 * np.log2(2 / 5) - 3 / 5 * np.log2(3 / 5)\n",
    "HD3 = -1 / 5 * np.log2(1 / 5) - 4 / 5 * np.log2(4 / 5)\n",
    "print('H(D1):', HD1)\n",
    "print('H(D2):', HD2)\n",
    "print('H(D3):', HD3)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p1 0.3333333333333333\n",
      "p2 0.3333333333333333\n",
      "p3 0.3333333333333333\n"
     ]
    }
   ],
   "source": [
    "p = 5 / 15\n",
    "print('p1', p)\n",
    "print('p2', p)\n",
    "print('p3', p)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H(D|年龄)= 0.8879430945988998\n"
     ]
    }
   ],
   "source": [
    "HDA1 = p * HD1 + p * HD2 + p * HD3\n",
    "print('H(D|年龄)=', HDA1)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H(D|有工作)= 0.6473003963031123\n"
     ]
    }
   ],
   "source": [
    "# 有工作：有 5(否0 是5) ； 否 10(否6 是4)\n",
    "p1 = 5 / 15\n",
    "p2 = 10 / 15\n",
    "# 否为0，意味着不确定性为哦，所以熵为0\n",
    "HDA2 = p1 * 0 + p2 * (-6 / 10 * np.log2(6 / 10) - 4 / 10 * np.log2(4 / 10))\n",
    "print('H(D|有工作)=', HDA2)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H(D|有自己的房子)= 0.5509775004326937\n"
     ]
    }
   ],
   "source": [
    "# 有自己的房子： 是 6(0否 6是) ； 否 9(3否 6是)\n",
    "HDA3 = 6 / 15 * 0 + 9 / 15 * (-3 / 9 * np.log2(3 / 9) - 6 / 9 * np.log2(6 / 9))\n",
    "print('H(D|有自己的房子)=', HDA3)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H(D|信贷情况)= 0.6079610319175832\n"
     ]
    }
   ],
   "source": [
    "# 信贷情况： 非常好 4(否0 是4) ； 好 6(否2 是4) ； 一般 5(否4 是1)\n",
    "HDA4 = 4 / 15 * 0 + 6 / 15 * (-2 / 6 * np.log2(2 / 6) - 4 / 6 * np.log2(4 / 6)) + 5 / 15 * (\n",
    "        -4 / 5 * np.log2(4 / 5) - 1 / 5 * np.log2(1 / 5))\n",
    "print('H(D|信贷情况)=', HDA4)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### 信息增益 g(D,A)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "g(D,年龄)=0.08300749985576883\n",
      "g(D,有工作)=0.32365019815155627\n",
      "g(D,有自己的房子)=0.4199730940219749\n",
      "g(D,信贷情况)=0.36298956253708536\n"
     ]
    }
   ],
   "source": [
    "# g(D,A) = H(D)-H(D|A)\n",
    "# 信息增益：得知特征A而使对训练集D进行分类的不确定性减少的程度\n",
    "# 有时候倾向于选择具有更多取值的特征\n",
    "# e.g. 有工作的取值为是，否两种；信贷情况的取值为非常好，好，一般三种。信贷情况的增益比>有工作的增益比\n",
    "gDA1 = HD - HDA1\n",
    "gDA2 = HD - HDA2\n",
    "gDA3 = HD - HDA3\n",
    "gDA4 = HD - HDA4\n",
    "print('g(D,年龄)={}\\ng(D,有工作)={}\\ng(D,有自己的房子)={}\\ng(D,信贷情况)={}'.format(gDA1, gDA2, gDA3, gDA4))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "###  2、信息增益比"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "outputs": [
    {
     "data": {
      "text/plain": "0.05237190142858302"
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 在信息增益的基础上增加惩罚项，消除特征所具有的取值个数所带来的影响\n",
    "# 信息增益比： 倾向于选择所具有更少取值的特征\n",
    "# g(D,A)/HA(D): 特征A单位取值个数下的信息增益\n",
    "# 年龄A1\n",
    "HA1D = -5 / 15 * np.log2(5 / 15) - 5 / 15 * np.log2(5 / 15) - 5 / 15 * np.log2(5 / 15)\n",
    "gDA1 / HA1D"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "outputs": [
    {
     "data": {
      "text/plain": "0.3524465495205019"
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 有工作 A2\n",
    "HA2D = -5 / 15 * np.log2(5 / 15) - 10 / 15 * np.log2(10 / 15)\n",
    "gDA2 / HA2D"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "outputs": [
    {
     "data": {
      "text/plain": "0.4325380677663126"
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 有自己的房子 A3\n",
    "HA3D = -6 / 15 * np.log2(6 / 15) - 9 / 15 * np.log2(9 / 15)\n",
    "gDA3 / HA3D"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "outputs": [
    {
     "data": {
      "text/plain": "0.2318538812872422"
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 信贷情况 A4\n",
    "HA4D = -4 / 15 * np.log2(4 / 15) - 6 / 15 * np.log2(6 / 15) - 5 / 15 * np.log2(5 / 15)\n",
    "gDA4 / HA4D"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "###  3、基尼指数"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "outputs": [],
   "source": [
    "# 详见CART的代码"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "##  决策树的生成"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "outputs": [],
   "source": [
    "# ID3 (信息增益)\n",
    "# C4.5 (信息增益比)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### ID3"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "outputs": [],
   "source": [
    "# 利用ID3生成贷款数据样本的决策树,假设阈值为0.001\n",
    "# step1、训练数据数据集D 分类取值为是、否，不属于同一类且具有4个特征值\n",
    "# step2、选择信息增益最大的特征Ag ： 有自己的房子\n",
    "# step3、Ag将D分为D1(是)和D2(否)；D1是只有一个分类，D2有两个分类，对D2继续重复以上步骤\n",
    "# 此时的训练集为：D2 特征集为：{A1，A2,A4}"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "outputs": [
    {
     "data": {
      "text/plain": "0.9182958340544896"
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# H(D2)\n",
    "HD2 = -6 / 9 * np.log2(6 / 9) - 3 / 9 * np.log2(3 / 9)\n",
    "HD2"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "outputs": [],
   "source": [
    "# H(D2|A1)=4/9*H(D21)+2/9*H(D22)+3/9*H(D23)\n",
    "HD21 = -1 / 4 * np.log2(1 / 4) - 3 / 4 * np.log2(3 / 4)\n",
    "HD22 = 0\n",
    "HD23 = -2 / 3 * np.log2(2 / 3) - 1 / 3 * np.log2(1 / 3)\n",
    "HD2A1 = 4 / 9 * HD21 + 2 / 9 * HD22 + 3 / 9 * HD23"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "outputs": [
    {
     "data": {
      "text/plain": "0.2516291673878229"
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 年龄 信息增益\n",
    "# g(D2,A1)=H(D2)-H(D2|A1)\n",
    "gD2A1 = HD2 - HD2A1\n",
    "gD2A1"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "outputs": [
    {
     "data": {
      "text/plain": "0.9182958340544896"
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 有工作\n",
    "# H(D2|A2)=3/9*H(D21)+6/9*H(D22)\n",
    "HD21 = 0\n",
    "HD22 = 0\n",
    "# g(D2,A2)=H(D2)-H(D2|A2)\n",
    "gD2A2 = HD2 - 0\n",
    "gD2A2"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "outputs": [
    {
     "data": {
      "text/plain": "0.47385138961004514"
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 信贷情况\n",
    "# H(D2|A4)=1/9*H(D21)+4/9*H(D22)+4/9*H(D23)\n",
    "HD21 = 0\n",
    "HD22 = -2 / 4 * np.log2(2 / 4) - 2 / 4 * np.log2(2 / 4)\n",
    "HD23 = 0\n",
    "HD2A4 = 1 / 9 * HD21 + 4 / 9 * HD22 + 4 / 9 * HD23\n",
    "# g(D2,A4)=H(D2)-H(D2|A4)\n",
    "gD2A4 = HD2 - HD2A4\n",
    "gD2A4"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "##### • 综上应选择A2(有工作)作为新的Ag,将D2进行划分；D1为是，D2为否，且D1和D2都是单类，决策树生成"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### CART"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.43999999999999995\n"
     ]
    }
   ],
   "source": [
    "# 训练数据集D，特征集A，阈值ε\n",
    "# 以年龄作为Ag时，对可能取到的每个值ag进行基尼指数的计算\n",
    "# 青年 D1; 非青年 D2(在ag1=青年的情况下)\n",
    "GimiD1 = 2 * (2 / 5) * (3 / 5)\n",
    "GimiD2 = 2 * (7 / 10) * (3 / 10)\n",
    "GimiDA = 5 / 15 * GimiD1 + 10 / 15 * GimiD2\n",
    "print(GimiDA)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.4799999999999999\n"
     ]
    }
   ],
   "source": [
    "# 中年 D1; 非中年 D2(在ag2=中年的情况下)\n",
    "GimiD1 = 2 * (3 / 5) * (2 / 5)\n",
    "GimiD2 = 2 * (6 / 10) * (4 / 10)\n",
    "GimiDA = 5 / 15 * GimiD1 + 10 / 15 * GimiD2\n",
    "print(GimiDA)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.44\n"
     ]
    }
   ],
   "source": [
    "# 老年 D1; 非老年 D2(在ag3=老年的情况下)\n",
    "GimiD1 = 2 * (1 / 5) * (4 / 5)\n",
    "GimiD2 = 2 * (5 / 10) * (5 / 10)\n",
    "GimiDA = 5 / 15 * GimiD1 + 10 / 15 * GimiD2\n",
    "print(GimiDA)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "##### • 在年龄这个特征下，所得到的的基尼指数为Gimi(D|A)=0.44,最优划分点可以是青年或者老年"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.31999999999999995\n"
     ]
    }
   ],
   "source": [
    "# Ag=有工作\n",
    "GimiD1 = 2 * (2 / 5) * 0\n",
    "GimiD2 = 2 * (4 / 10) * (6 / 10)\n",
    "GimiDA = 5 / 15 * GimiD1 + 10 / 15 * GimiD2\n",
    "print(GimiDA)\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.26666666666666666\n"
     ]
    }
   ],
   "source": [
    "# Ag=有自己的房子\n",
    "GimiD1 = 0\n",
    "GimiD2 = 2 * (6 / 9) * (3 / 9)\n",
    "GimiDA = 6 / 15 * GimiD1 + 9 / 15 * GimiD2\n",
    "print(GimiDA)\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.3636363636363636\n"
     ]
    }
   ],
   "source": [
    "# Ag=有自己的房子\n",
    "# ag1=非常好\n",
    "GimiD1 = 0\n",
    "GimiD2 = 2 * (5 / 11) * (6 / 11)\n",
    "GimiDA = 4 / 15 * GimiD1 + 11 / 15 * GimiD2\n",
    "print(GimiDA)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.4641975308641975\n"
     ]
    }
   ],
   "source": [
    "# ag2=好\n",
    "GimiD1 = 2 * (2 / 6) * (4 / 6)\n",
    "GimiD2 = 2 * (4 / 9) * (5 / 9)\n",
    "GimiDA = 9 / 15 * GimiD1 + 6 / 15 * GimiD2\n",
    "print(GimiDA)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.32000000000000006\n"
     ]
    }
   ],
   "source": [
    "# ag3=一般\n",
    "GimiD1 = 2 * (4 / 5) * (1 / 5)\n",
    "GimiD2 = 2 * (2 / 10) * (8 / 10)\n",
    "GimiDA = 5 / 15 * GimiD1 + 10 / 15 * GimiD2\n",
    "print(GimiDA)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "\n",
    "##### • 在’信贷情况‘这个特征下，所得到的的基尼指数为Gimi(D|A)=0.32,最优划分点可以是一般\n",
    "##### • 综上，最优特征是‘有自己的房子’，进行划分，重复上述步骤，直到没有更多特征了"
   ],
   "metadata": {
    "collapsed": false
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}